package com.fr.lintcode;

import java.util.TreeSet;

import org.junit.Test;

public class Q1690ii {


	/**
	 * @param val: the personality value of user
	 * @return: Return their recommend friends' value
	 * 超时
	 */
	public int[] getAns(int[] val) {
		// Write your code here
		if (val == null || val.length <= 1) {
			return new int[0];
		}
		int length = val.length;
		TreeSet<Integer> set = new TreeSet<>();
		int[] rs = new int[length - 1];
		set.add(val[0]);
		for(int i = 1; i < length; i++) {
			rs[i - 1] = getVal(set, val[i]);
			set.add(val[i]);
		}
		return rs;
	}

	private int getVal(TreeSet<Integer> set, int i) {
		Integer max = set.ceiling(i);
		if(max == null) {
			return set.last();
		}
		Integer min = set.lower(i);
		if(min == null) {
			return max;
		}
		if(min + max >= 2 *i) {
			return min;
		}else {
			return max;
		}
	}

	
	@Test
	public void testA() {
		int val[] = {42513,634109,796545,10042,858796,798261,965961,251849};
		int rs[] = getAns(val);
		for(int s : rs) {
			System.out.print(s +",");
		}
		
	}

}
